#include <algorithm>
#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

/**
 * @方法: 双指针
 * @时间复杂度: o(n^2)
 * @空间复杂度: o(1)
 * @评价: 固定第一重循环，二、三重循环设左、右双指针。注意去重。
 */
vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    int target = 0;

    vector<vector<int>> ans;
    for (int i = 0; i < n; ++i) {
        if (i >= 1 && nums[i] == nums[i - 1])
            continue;

        int k = n - 1;  // 右指针
        // 左指针的移动
        for (int j = i + 1; j < n; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1])
                continue;

            // 右指针的移动
            while (nums[i] + nums[j] + nums[k] > target && j < k) {
                k--;
            }
            if (j == k)
                break;  // 想想这里为什么不是 return ans

            if (nums[i] + nums[j] + nums[k] == target) {
                ans.push_back({nums[i], nums[j], nums[k]});
            }
        }
    }
    return ans;
}

int main() {
    cout << "hello world" << endl;
    return 0;
}